#include <cstdio>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

typedef vector<vector<int>> SudokuGrid;
typedef vector<vector<vector<int>>> SudokuCandidates;

// 预处理公共模块：计算行列宫的已用数字
void computeUsed(const SudokuGrid& grid,
                vector<vector<bool>>& row_used,
                vector<vector<bool>>& col_used,
                vector<vector<bool>>& box_used) {
    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            int num = grid[row][col];
            if (num != 0) {
                row_used[row][num] = true;
                col_used[col][num] = true;
                int box = (row / 3) * 3 + (col / 3);
                box_used[box][num] = true;
            }
        }
    }
}

// 公共候选值生成模块（Possible Number核心逻辑）
SudokuCandidates generateBaseCandidates(const SudokuGrid& grid,
                                        const vector<vector<bool>>& row_used,
                                        const vector<vector<bool>>& col_used,
                                        const vector<vector<bool>>& box_used) {
    SudokuCandidates candidates(9, vector<vector<int>>(9));
    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            if (grid[row][col] == 0) {
                vector<int> possible;
                for (int num = 1; num <= 9; ++num) {
                    int box = (row / 3) * 3 + (col / 3);
                    if (!row_used[row][num] && 
                        !col_used[col][num] && 
                        !box_used[box][num]) {
                        possible.push_back(num);
                    }
                }
                candidates[row][col] = possible;
            }
        }
    }
    return candidates;
}

// Possible Number策略实现
SudokuCandidates possibleNumberInference(const SudokuGrid& grid) {
    vector<vector<bool>> row_used(9, vector<bool>(10, false));
    vector<vector<bool>> col_used(9, vector<bool>(10, false));
    vector<vector<bool>> box_used(9, vector<bool>(10, false));
    computeUsed(grid, row_used, col_used, box_used);
    return generateBaseCandidates(grid, row_used, col_used, box_used);
}

// Last Remaining Cell策略实现
SudokuCandidates lastRemainingCellInference(const SudokuGrid& grid) {
    // 复用Possible Number的预处理和候选值生成
    auto candidates = possibleNumberInference(grid);

    // 检查行中的唯一候选
    auto checkRegion = [&](const vector<pair<int, int>>& cells) {
        map<int, vector<pair<int, int>>> num_map;
        for (auto [r, c] : cells) {
            for (int num : candidates[r][c]) {
                num_map[num].emplace_back(r, c);
            }
        }
        for (auto& [num, positions] : num_map) {
            if (positions.size() == 1) {
                auto [row, col] = positions[0];
                candidates[row][col] = {num}; // 锁定唯一候选值
            }
        }
    };

    // 检查所有行、列、宫格
    for (int i = 0; i < 9; ++i) {
        // 行检查
        vector<pair<int, int>> row_cells;
        for (int col = 0; col < 9; ++col) 
            if (grid[i][col] == 0) row_cells.emplace_back(i, col);
        checkRegion(row_cells);

        // 列检查
        vector<pair<int, int>> col_cells;
        for (int row = 0; row < 9; ++row)
            if (grid[row][i] == 0) col_cells.emplace_back(row, i);
        checkRegion(col_cells);

        // 宫格检查
        vector<pair<int, int>> box_cells;
        int start_row = (i / 3) * 3;
        int start_col = (i % 3) * 3;
        for (int r = 0; r < 3; ++r)
            for (int c = 0; c < 3; ++c)
                if (grid[start_row + r][start_col + c] == 0)
                    box_cells.emplace_back(start_row + r, start_col + c);
        checkRegion(box_cells);
    }
    return candidates;
}

void print(SudokuCandidates grid) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            printf("[%d, %d]: ", row, col);
            for (auto v: grid[row][col]) {
                printf("%d ",v);
            }
            printf("\n");
        }
    }
    return;
}

int main()
{
    /*
    SudokuGrid grid = {
        {2,0,0,0,7,0,0,3,8},
        {0,0,0,0,0,6,0,7,0},
        {3,0,0,0,4,0,6,0,0},
        {0,0,8,0,2,0,7,0,0},
        {1,0,0,0,0,0,0,0,6},
        {0,0,7,0,3,0,4,0,0},
        {0,0,4,0,8,0,0,0,9},
        {0,6,0,4,0,0,0,0,0},
        {9,1,0,0,6,0,0,0,2}
    };
    */

    SudokuGrid grid = {
        {3,8,0,0,0,0,0,0,6},
        {0,0,0,6,0,4,0,0,8},
        {0,0,4,1,0,0,0,2,0},
        {0,7,0,3,2,0,0,8,0},
        {0,0,0,0,0,0,0,0,0},
        {0,5,0,0,4,6,0,9,0},
        {0,3,0,0,0,0,2,0,0},
        {5,0,0,7,0,9,0,0,0},
        {1,0,0,0,0,0,0,6,7}
    };

    freopen("output2.txt", "w", stdout);

    printf("possibleNumberInference\n");
    
    auto possible = possibleNumberInference(grid);

    print(possible);

    printf("lastRemainingCellInference\n");

    auto refined = lastRemainingCellInference(grid);

    print(refined);

    return 0;
}